package stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*思路
  1.先将表达式，放入一个ArrayList 中
  2.将 ArrayList 传递给一个方法，配合栈完成计算(遍历ArrayList)
*/
public class PolandNotaion {
	public static void main(String[] args) {
        /*把一个中缀表达式，转换为后缀表达式
          1. 1+（（2+3）*4）-5 => 1 2 3 + 4 * + 5 -
          2. 直接对字符串进行操作不方便，所以先把字符串转成中缀的列表
             即把字符串变为 ArrayList，后面对ArrayList操作
          3.把得到的中缀表达式转换成后缀表达式
         */
		String expression = "1+((2+3)*4)-5";
		List<String> infixExpressionList = toInfixExpressionList(expression);
		System.out.println(infixExpressionList);
		System.out.println("==========");
		List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
		System.out.println(parseSuffixExpressionList);
		System.out.println(calculate(parseSuffixExpressionList));


//        //定义一个逆波兰表达式(后缀表达式)
//        //(30+4)*5-6 => 30 4 + 5 6 -
//        //4*5-8+60+8/2 => 4 5 * 8 2 / + 8 - 60 +
//        String suffixExpression = "4 5 * 8 2 / + 8 - 60 +";
//
//        List<String> list = getListString(suffixExpression);
//        System.out.println(list);
//
//        int res = calculate(list);
//        System.out.println(res);
	}

	//将中缀表达式转换成对应的List
	public static List<String> toInfixExpressionList(String s) {
		//定义一个List
		List<String> list = new ArrayList<>();
		int i = 0;//用于遍历字符串的指针
		String str = "";//用于拼接字符串
		char c = ' ';
		while (i < s.length()) {
			//如果 c 是一个非数字，就需要加入到 list
			if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
				list.add("" + c);
				i++;
			} else {//如果是一个数字，考虑多位数的问题
				str = "";
				while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
					str += c;
					i++;
				}
				list.add(str);
			}
		}
		return list;
	}

	//把中缀表达式，转换成后缀表达式
	public static List<String> parseSuffixExpressionList(List<String> list) {
		//初始化两个栈
		Stack<String> s1 = new Stack<>();//符号栈
		List<String> s2 = new ArrayList<>();//存储中间结果(即后缀表达式)

		//遍历 list
		for (String item : list) {
			//如果是一个数，加入s2
			if (item.matches("\\d+")) {
				s2.add(item);
			} else if (item.equals("(")) {
				s1.push(item);
			} else if (item.equals(")")) {
				while (!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				s1.pop();//将对应的一对（）弹出
			} else {
				//当 item 的优先级 <=  栈顶优先级，把 s1 栈顶的运算符弹出，并加入s2
				while (s1.size() != 0 && pripority(item) <= pripority(s1.peek())) {
					s2.add(s1.pop());
				}
				//把 item 压入栈
				s1.push(item);
			}

		}
		//最后把 s1 中剩余的运算符加入 s1
		while (s1.size() > 0) {
			s2.add(s1.pop());
		}
		return s2;
	}

	//将一个逆波兰表达式,依次将数据和运算符，放入到一个ArrayList中
	public static List<String> getListString(String suffixExpression) {
		//将 suffixExpression 分割
		String[] splist = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for (String ele : splist) {
			list.add(ele);
		}
		return list;
	}

	//完成对逆波兰表达式的运算
	public static int calculate(List<String> list) {
		//创建栈，一个栈
		Stack<String> stack = new Stack<>();
		//遍历
		for (String item : list) {
			//使用正则表达式取出数
			if (item.matches("\\d+")) {//匹配多位数
				stack.push(item);
			} else {
				//如果不是数，pop两个数并运算,将结果在入栈
				int num1 = Integer.parseInt(stack.pop());
				int num2 = Integer.parseInt(stack.pop());
				int res = 0;
				if (item.equals("+")) {
					res = num2 + num1;
				} else if (item.equals("-")) {
					res = num2 - num1;
				} else if (item.equals("*")) {
					res = num2 * num1;
				} else if (item.equals("/")) {
					res = num2 / num1;
				} else {
					throw new RuntimeException("运算符有误");
				}
				//把 res 入栈,res+"" => 把数字 res 转成 String
				stack.push(res + "");
			}
		}
		//最后留在 栈 中的就是结果
		return Integer.parseInt(stack.pop());
	}

	public static int pripority(String ch) {
		if (ch.equals("+") || ch.equals("-")) {
			return 0;
		} else if (ch.equals("*") || ch.equals("/")) {
			return 1;
		} else {
			return -1;
		}
	}

}
